package com.zhang.study.chapter10;

import java.util.HashMap;
import java.util.Map;

// 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/
public class Code04_CopyListWithRandom {
    public static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }


    public Node copyRandomList1(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> cache = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            cache.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            cache.get(cur).next = cache.get(cur.next);
            cache.get(cur).random = cache.get(cur.random);
            cur = cur.next;
        }
        return cache.get(head);
    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next;
        Node copy;
        Node res;
        while (cur != null) {
            copy = new Node(cur.val);
            next = cur.next;
            copy.next = next;
            cur.next = copy;
            cur = next;
        }
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }
        res = head.next;
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            copy = cur.next;
            copy.next = next == null ? null : next.next;
            cur.next = next;
            cur = next;
        }
        return res;
    }


}
